
package search;
import java.util.*;
/**
 * Write a description of class DepthFirstSearchVisitor here.
 * 
 * @author (your name) 
 * @version (a version number or a date)
 */
public abstract class DepthFirstSearchVisitor<N extends GraphNode<?>, E extends GraphEdge<?,N>> implements SearchVisitor<N,E>
{

    private ArrayList<SearchNode<N>> toDo = new ArrayList<SearchNode<N>>();
    private ArrayList<SearchNode<N>> alreadyVisited = new ArrayList<SearchNode<N>>();
    
    public SearchNode<N> search(Digraph<N,E> graph)
    {
        N start = getStart();
        toDo.add(new SearchNode<N>(start,null,0,0));
        
        while (toDo.size() > 0) {
            //add new ones at end, and take ones at end first
            SearchNode<N> n = toDo.remove(toDo.size()-1);
            if (isGoal(n.getState())) {
                return n;
            }
            else {
                alreadyVisited.add(n);
                N state = n.getState();
                for (E edge : graph.getEdges(state)) {
                    SearchNode<N> newSn = new SearchNode<N>(edge.getOppositeEnd(state),n,n.getCost() + edge.getCost(),n.getDepth() + 1);
                    if (!(alreadyVisited.contains(newSn)) && !(toDo.contains(newSn))) {
                        toDo.add(newSn);
                    }
                }
            }
        }
        return null;
    }                           
}
